package org.raymond.iworks.study.basic.algorithm.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 注意:使用二分查找的前提是该数组是有序的
 * 思路分析
 * 0,数组:从左至右,从小到大
 * 1,首先确定该数组的中间的下标
 * 1.1, left,mid,right都是指向数组元素的下标
 * 1.2, mid=(left+right)/2
 * 2,然后让需要查找的数findVal和arr[mid]比较
 * 2.1 findVal > arr[mid], 说明要查找的数在mid的右边,因此需要递归的向右查找
 * 2.2 findVal < arr[mid], 说明要查找的数在mid的左边,因此需要递归的向左查找
 * 2.3 findVal == arr[mid], 说明找到,就返回
 * 3,递归必须要有结束递归的条件
 * 3.1 找到就结束递归
 * 3.2 递归完整个数组,仍然没有找到findVal,也需要结束递归
 * 3.3 当arr[left]>arr[right],即可能在移动指针的过程中,left向右移到了right的右边,
 * 或者right向左移到了left的左边,则需要结束递归
 */
public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,8,10,89,89,1000,1234};
        int findVal = 6;
        int idx = binarySearch0(arr, 0, arr.length-1, findVal);
        if(idx!=-1) {
            System.out.println("search idx: " + idx + " value: " + arr[idx]);
        }else{
            System.out.println("can not find value: "+findVal+" in arr");
        }

        List<Integer> idxList = binarySearch(arr, 0, arr.length-1, findVal);
        if(idxList!=null) {
            System.out.println("search idx: " + idxList + " value: " + arr[idxList.get(0)]);
        }else{
            System.out.println("can not find value: "+findVal+" in arr");
        }
    }


    // 前提: 数组:从左至右,从小到大
    // 如果找到,则返回下标,如果没有找到,则返回-1
    public static int binarySearch0(int[] arr, int left, int right, int findVal){
        // 当left>right时,说明递归整个数组,但是没有找到
        if(left>right){
            return -1;
        }
        int mid = (left+right)/2;
        int midVal = arr[mid];

        if(findVal>midVal){
            // 向右递归
            return binarySearch0(arr, mid+1, right, findVal);
        }else if(findVal<midVal){
            // 向左递归
            return binarySearch0(arr, left, mid-1, findVal);
        }else {
            return mid;
        }
    }

    /**
     * 思考题: {1,8,10,89,1000,1000,1234},当一个有序数组中,有多个相同的数值时,
     * 如何将所有的数值都查找到
     *
     * 思路分析:
     * 1,在找到mid索引值时,不要马上返回
     * 2,向mid索引值的左边扫描,将所有满足条件的元素的下标,加入到list中
     * 3,向mid索引值的右边扫描,将所有满足条件的元素的下标,加入到list中
     * 4,返回list
     */
    public static List<Integer> binarySearch(int[] arr, int left, int right, int findVal){
        // 当left>right时,说明递归整个数组,但是没有找到
        if(left>right){
            return null;
        }

        int mid = (left+right)/2;
        int midVal = arr[mid];

        if(findVal>midVal){
            // 向右递归
            return binarySearch(arr, mid+1, right, findVal);
        }else if(findVal<midVal){
            // 向左递归
            return binarySearch(arr, left, mid-1, findVal);
        }else {
            List<Integer> list = new ArrayList<>();
            // 向mid索引值的左边扫描,将所有满足条件的元素的下标,加入到list中
            int temp = mid-1;
            while(true){
                if(temp<0||arr[temp]!=findVal){
                    break;
                }
                // 否则,将temp放入list中
                list.add(temp);
                // temp 左移
                temp-=1;
            }
            list.add(mid);
            // 向mid索引值的右边扫描,将所有满足条件的元素的下标,加入到list中
            temp = mid+1;
            while(true){
                if(temp>arr.length-1||arr[temp]!=findVal){
                    break;
                }
                // 否则,将temp放入list中
                list.add(temp);
                // temp右移
                temp+=1;
            }
            return list;
        }
    }
}
